package t42

import (
	"fmt"
	"sort"
	"sync"
)

type MyStack struct {
	items []int
	l     sync.Mutex
}

func (s *MyStack) Push(n int) bool {
	s.l.Lock()
	defer s.l.Unlock()
	s.items = append(s.items, n)
	return true
}

func (s *MyStack) Pop() (int, bool) {
	s.l.Lock()
	defer s.l.Unlock()
	if len(s.items) == 0 {
		return 0, false
	}
	el := s.items[len(s.items)-1]
	s.items = s.items[:len(s.items)-1]
	return el, true
}

func (s *MyStack) Top() (int, bool) {
	s.l.Lock()
	defer s.l.Unlock()
	if len(s.items) == 0 {
		return 0, false
	}
	el := s.items[len(s.items)-1]
	return el, true
}

func (s *MyStack) Head() (int, bool) {
	s.l.Lock()
	defer s.l.Unlock()
	if len(s.items) == 0 {
		return 0, false
	}
	el := s.items[0]
	return el, true
}

func (s *MyStack) Clear() bool {
	s.l.Lock()
	defer s.l.Unlock()
	s.items = s.items[0:0]
	return true
}

func (s MyStack) Size() int {
	return len(s.items)
}

func (s MyStack) Show() {
	fmt.Println(s.items)
}

func trap(height []int) int {

	var wg sync.WaitGroup
	stack := &MyStack{}
	sum := 0

	for _, v := range height {
		var tmp []int
		head, ok := stack.Head()
		if ok {
			if head > v {
				stack.Push(v)
			} else {
				stack.Push(v)
				for _, v := range stack.items {
					tmp = append(tmp, v)
				}
				stack.Clear()
				stack.Push(v)
				if len(tmp) >= 3 {
					wg.Add(1)
					go func() {
						sum += calCnt(tmp)
						wg.Done()
					}()
				}

				continue
			}
		} else {
			if v == 0 {
				continue
			}
			stack.Push(v)
		}
	}

	if len(stack.items) >= 3 {
		// 最后的窗口处理一下尾部
		for true {
			el, b := stack.Pop()
			if b {
				if t, ok := stack.Top(); ok && el > t {
					stack.Push(el)
					break
				}
			} else {
				break
			}

		}
		if stack.Size() != 0 {
			tmp := stack.items
			wg.Add(1)
			go func() {
				sum += calCnt(tmp)
				wg.Done()
			}()

		}
	}

	wg.Wait()

	return sum
}

func calCnt(s []int) int {
	cnt := 0
	sorted := make([]int, len(s))
	copy(sorted, s)
	sort.Sort(sort.Reverse(sort.IntSlice(sorted)))
	max := sorted[0]

	for i := 0; i < max; i++ {
		start := -1
		end := -1

		tmp := make([]int, len(s))
		copy(tmp, s)

		for j := 0; j < len(s); j++ {
			if s[j] != 0 {
				if start == -1 {
					start = j
				}
				end = j
				s[j]--
			}
		}

		if start == -1 || end == -1 {
			continue
		}

		calSlice := tmp[start : end+1]

		if len(calSlice) >= 3 {
			for _, v := range calSlice {
				if v == 0 {
					cnt++
				}
			}
		}
	}

	return cnt
}
